{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Kth Smallest Number in Multiplication Table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findKthNumber"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #乘法表中第k小的数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>几乎每一个人都用&nbsp;<a href=\"https://baike.baidu.com/item/%E4%B9%98%E6%B3%95%E8%A1%A8\">乘法表</a>。但是你能在乘法表中快速找到第 <code>k</code> 小的数字吗？</p>\n",
    "\n",
    "<p>乘法表是大小为 <code>m x n</code> 的一个整数矩阵，其中&nbsp;<code>mat[i][j] == i * j</code>（下标从 <strong>1</strong> 开始）。</p>\n",
    "\n",
    "<p>给你三个整数 <code>m</code>、<code>n</code> 和 <code>k</code>，请你在大小为&nbsp;<code>m x n</code> 的乘法表中，找出并返回第 <code>k</code>&nbsp;小的数字。</p>\n",
    "\n",
    "<div class=\"original__bRMd\">\n",
    "<div>\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/05/02/multtable1-grid.jpg\" style=\"width: 500px; height: 254px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>m = 3, n = 3, k = 5\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>第 5 小的数字是 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/05/02/multtable2-grid.jpg\" style=\"width: 493px; height: 293px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>m = 2, n = 3, k = 6\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>第 6 小的数字是 6 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 3 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= m * n</code></li>\n",
    "</ul>\n",
    "</div>\n",
    "</div>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [kth-smallest-number-in-multiplication-table](https://leetcode.cn/problems/kth-smallest-number-in-multiplication-table/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [kth-smallest-number-in-multiplication-table](https://leetcode.cn/problems/kth-smallest-number-in-multiplication-table/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n3\\n5', '2\\n3\\n6']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        def cnt(mid,m,n): #计算当前矩阵中小于等于mid值的数字数量\n",
    "            ret,i,j = 0,m,1\n",
    "            while (i>=1 and j<=n):\n",
    "                if i*j<=mid: #当前值小于mid，则列数+1，多i个比mid小的\n",
    "                    ret += i\n",
    "                    j += 1\n",
    "                else: #当前值大于mid，则行数-1，直到当前值小于等于mid\n",
    "                    i-=1\n",
    "            return ret\n",
    "       \n",
    "        l,r = 1,m*n\n",
    "        while (l<r): #二分法，多的把右边砍一半，少了把左边砍一半\n",
    "            mid = (l+r)>>1  #右移一位，相当于（l+r）/2，但>>的速度比 / 效率高的多\n",
    "            if cnt(mid,m,n)<k: #要寻找第k小的，如果小于等于当前值的数量比k少，就增加当前值，增大左边界\n",
    "                l = mid+1\n",
    "            else: #要寻找第k小的，如果小于等于当前值的数量，大于等于k，就减少当前值，减小左边界\n",
    "                r = mid\n",
    "        return l\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        return bisect_left(range(m*n), k, key=lambda x:x //n * n + sum(x//i for i in range(x//n+1, m+1)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "         return bisect_left(range(m * n), k, key=lambda x: x // n * n + sum(x // i for i in range(x // n + 1, m + 1)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        R, C = m, n\n",
    "\n",
    "        def lt(x):\n",
    "            cnt = 0\n",
    "            for r in range(1, R + 1):\n",
    "                cnt += min(x // r, C)\n",
    "            return cnt < k\n",
    "\n",
    "\n",
    "        l, r = 1, R * C + 1\n",
    "        while l<r:\n",
    "            mid = (l + r) // 2\n",
    "            if lt(mid):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        def cnt(mid,m,n): #计算当前矩阵中小于等于mid值的数字数量\n",
    "            ret,i,j = 0,m,1\n",
    "            while (i>=1 and j<=n):\n",
    "                if i*j<=mid: #当前值小于mid，则列数+1，多i个比mid小的\n",
    "                    ret += i\n",
    "                    j += 1\n",
    "                else: #当前值大于mid，则行数-1，直到当前值小于等于mid\n",
    "                    i-=1\n",
    "            return ret\n",
    "       \n",
    "        l,r = 1,m*n\n",
    "        while (l<r): #二分法，多的把右边砍一半，少了把左边砍一半\n",
    "            mid = (l+r)>>1  #右移一位，相当于（l+r）/2，但>>的速度比 / 效率高的多\n",
    "            if cnt(mid,m,n)<k: #要寻找第k小的，如果小于等于当前值的数量比k少，就增加当前值，增大左边界\n",
    "                l = mid+1\n",
    "            else: #要寻找第k小的，如果小于等于当前值的数量，大于等于k，就减少当前值，减小左边界\n",
    "                r = mid\n",
    "        return l\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        def check(mid):\n",
    "            cnt = 0\n",
    "            x, y=m, 1\n",
    "            while x>0 and y<n+1:\n",
    "                if x*y<=mid:\n",
    "                    cnt += x\n",
    "                    y += 1\n",
    "                else: x -= 1\n",
    "            return cnt>=k\n",
    "        \n",
    "        left, right = 1, m*n\n",
    "        while left<right:\n",
    "            mid = (left+right)//2\n",
    "            if check(mid):\n",
    "                right = mid\n",
    "            else: left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        def cnt(mid,m,n): #计算当前矩阵中小于等于mid值的数字数量\n",
    "            ret,i,j = 0,m,1\n",
    "            while (i>=1 and j<=n):\n",
    "                if i*j<=mid: #当前值小于mid，则列数+1，多i个比mid小的\n",
    "                    ret += i\n",
    "                    j += 1\n",
    "                else: #当前值大于mid，则行数-1，直到当前值小于等于mid\n",
    "                    i-=1\n",
    "            return ret\n",
    "       \n",
    "        l,r = 1,m*n\n",
    "        while (l<r): #二分法，多的把右边砍一半，少了把左边砍一半\n",
    "            mid = (l+r)>>1  #右移一位，相当于（l+r）/2，但>>的速度比 / 效率高的多\n",
    "            if cnt(mid,m,n)<k: #要寻找第k小的，如果小于等于当前值的数量比k少，就增加当前值，增大左边界\n",
    "                l = mid+1\n",
    "            else: #要寻找第k小的，如果小于等于当前值的数量，大于等于k，就减少当前值，减小左边界\n",
    "                r = mid\n",
    "        return l\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        def check(x):\n",
    "            cnt = 0\n",
    "            l = 1\n",
    "            r = m\n",
    "            while 0 < l <= n and 0 < r <= m:\n",
    "                while r > 0 and l * r > x:\n",
    "                    r -= 1\n",
    "                cnt += r \n",
    "                l += 1\n",
    "            return cnt >= k\n",
    "\n",
    "\n",
    "        l = 1\n",
    "        r = m * n\n",
    "\n",
    "        while l < r:\n",
    "            mid = l + r >> 1\n",
    "            if check(mid): r = mid \n",
    "            else: l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        \"\"\"\n",
    "        二分：l = 1,r = m*n \n",
    "        然后统计小于等于mid的元素个数\n",
    "        统计的时候从左下角开始搜索,逐渐压缩范围\n",
    "        \"\"\"\n",
    "        def count(mid):\n",
    "            rs = 0\n",
    "            i,j = m,1\n",
    "            while i>=1 and j<=n:\n",
    "                if mid>=i*j:\n",
    "                    rs += i #说明这一列上方的也都小于mid\n",
    "                    j += 1 #下一列向右比较 \n",
    "                else:\n",
    "                    i -= 1 #向上一行 找更小的值\n",
    "            return rs\n",
    "        \n",
    "        l,r = 1,m*n\n",
    "        while l<r:\n",
    "            mid = (l+r)>>1\n",
    "            if count(mid) < k:\n",
    "                l = mid+1\n",
    "            else:\n",
    "                r = mid\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\r\n",
    "        left=0\r\n",
    "        right=m*n\r\n",
    "        while left<right:\r\n",
    "            mid=(left+right)//2\r\n",
    "            less_cnt=mid//n*n\r\n",
    "            for i in range(mid//n+1,m+1):\r\n",
    "                less_cnt+=mid//i\r\n",
    "            if less_cnt<k:\r\n",
    "                left=mid+1\r\n",
    "            else:\r\n",
    "                right=mid\r\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        left = 1\n",
    "        right = m * n\n",
    "        while left < right:\n",
    "            x = left + int((right - left) / 2)\n",
    "            count = int(x / n) * n\n",
    "            start = int(x / n) + 1\n",
    "            for i in range(start,m+1):\n",
    "                count += int(x / i)\n",
    "            if count >= k:\n",
    "                right = x\n",
    "            else:\n",
    "                left = x + 1\n",
    "        return left\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        \n",
    "        def small_or_equal(mid):\n",
    "            i, j = 1, n\n",
    "            c, x = 0, float('-inf')\n",
    "            while i <= m and j >= 1:\n",
    "                if i * j > mid:\n",
    "                    j -= 1\n",
    "                else:\n",
    "                    c += j\n",
    "                    x = max(x, i * j)\n",
    "                    i += 1\n",
    "            return c, x\n",
    "        \n",
    "        if k == 1:\n",
    "            return 1\n",
    "        if k == m * n:\n",
    "            return m * n\n",
    "        s, e = 1, m * n + 1\n",
    "        while s < e:\n",
    "            mid = (s + e) // 2\n",
    "            c, x = small_or_equal(mid)\n",
    "            if c == k:\n",
    "                return x\n",
    "            if c < k:\n",
    "                s = mid + 1\n",
    "            else:\n",
    "                e = mid\n",
    "        return small_or_equal(s)[1]\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def check(self, m, n, nums):\n",
    "        return sum(min(nums // i, n) for i in range(1, m + 1))\n",
    "\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        if k == 1:\n",
    "            return 1\n",
    "        if k == m * n:\n",
    "            return m * n\n",
    "        left, right = 1, m * n\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if self.check(m, n, mid) >= k:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left\n",
    "        \n",
    "#如何统计比mid小的数有多少个？\n",
    "# 形式化第i行的数为 [1*i, 2*i, 3*i, ..., k*i, ..., n*i]，每一行都有n个数。 假设此时第k个数 k*i 小于等于mid，所# 以k*i <= mid, k = mid // i，说明这行比小于等于mid的数有k个。 当 k<n时，说明此行有k个数小于等于mid，当 k>=n # # 时，说明此行的n个数都小于等于mid。 最后遍历所有行，统计所有小于等于mid的数都多少个。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        left, right = 1, m * n\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            cnt = 0\n",
    "            i, j = 1, n\n",
    "            while i <= m and j >= 1:\n",
    "                while j >= 1 and i * j > mid:\n",
    "                    j -= 1\n",
    "                cnt += j\n",
    "                i += 1\n",
    "            if cnt < k:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\\\n",
    "\n",
    "\n",
    "        def cnt(t):\n",
    "            x=m\n",
    "            y=1\n",
    "            ans=0\n",
    "            while y<=n and x>=1:\n",
    "                if x*y<=t:\n",
    "                    ans+=x\n",
    "                    y=y+1\n",
    "                else:\n",
    "                    x=x-1\n",
    "            return ans\n",
    "        print(cnt(439))\n",
    "        l=1\n",
    "        r=m*n\n",
    "        while l+1<r:\n",
    "            mid=(l+r)//2\n",
    "            if cnt(mid)<k:\n",
    "                l=mid\n",
    "            elif cnt(mid)>=k:\n",
    "                r=mid\n",
    "            #elif cnt(mid)==k:\n",
    "                #print(mid)\n",
    "                #print(cnt)\n",
    "               # return mid\n",
    "        #print(r,l)\n",
    "        return r\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\r\n",
    "class Solution:\r\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\r\n",
    "        return bisect_left(range(m*n), k ,key=lambda x: x//n*n+sum(x//i for i in range(x//n+1,m+1)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cnt(self, mid, m, n):\n",
    "        ret, i, j = 0, m, 1\n",
    "        while(i >= 1 and j <= n):\n",
    "            if i*j <= mid:\n",
    "                ret += i\n",
    "                j += 1\n",
    "            else:\n",
    "                i -= 1\n",
    "        return ret\n",
    "\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        l, r = 1, m*n\n",
    "        while(l < r):\n",
    "            mid = (l+r) >> 1\n",
    "            if(self.cnt(mid, m, n) < k):\n",
    "                l = mid+1\n",
    "            else:\n",
    "                r = mid\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        l,r = 1,m*n \n",
    "        def check(l,r,mid):\n",
    "            cnt = 0\n",
    "            for i in range(1,m+1):\n",
    "                cnt += min(n,mid//i)\n",
    "            return cnt\n",
    "\n",
    "\n",
    "        while l <r:\n",
    "            mid = (l+r)//2\n",
    "            if check(l,r,mid)>=k:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid+1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        return bisect_left(range(m * n), k, key=lambda x: x // n * n + sum(x // i for i in range(x // n + 1, m + 1)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        if n < m:\n",
    "            m, n = n, m\n",
    "        \n",
    "        def valid(num):\n",
    "            res = 0\n",
    "            for i in range(1, min(m, num) + 1):\n",
    "                res += min(n, num // i)\n",
    "            return res >= k\n",
    "        \n",
    "        left, right = 1, m * n\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if valid(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        left = 1\n",
    "        right = m*n\n",
    "        mid = (left+right)//2\n",
    "        while left < right:\n",
    "            now = mid //n * n + sum(mid//i for i in range(mid//n+1, m+1))\n",
    "            if now < k:\n",
    "                left = mid+1\n",
    "            else:\n",
    "                right = mid\n",
    "            mid = (left+right)//2\n",
    "        return mid\n",
    "        \n",
    "        # return bisect_left(range(m*n), k, key=lambda x:x //n * n + sum(x//i for i in range(x//n+1, m+1)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        def check(x):\n",
    "            cnt = 0\n",
    "            for i in range(1, n+1):\n",
    "                l = 1\n",
    "                r = m \n",
    "                while l < r:\n",
    "                    mid = l + r + 1 >> 1\n",
    "                    if i * mid <= x: l = mid \n",
    "                    else: r = mid - 1\n",
    "                if l * i <= x: cnt += l \n",
    "            return cnt >= k \n",
    "        l = 1\n",
    "        r = m * n\n",
    "\n",
    "        while l < r:\n",
    "            mid = l + r >> 1\n",
    "            if check(mid): r = mid \n",
    "            else: l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cnt(self, mid, m, n):\n",
    "        ret, i, j = 0, m, 1\n",
    "        while(i >= 1 and j <= n):\n",
    "            if i*j <= mid:\n",
    "                ret += i\n",
    "                j += 1\n",
    "            else:\n",
    "                i -= 1\n",
    "        return ret\n",
    "\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        l, r = 0,m*n + 1\n",
    "        while l + 1 < r:\n",
    "            mid = (l+r) >> 1\n",
    "            if(self.cnt(mid, m, n) < k):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        def helper(m,n,num):\n",
    "            count = 0\n",
    "\n",
    "            for i in range(1, m+1):\n",
    "                # for j in range(1,n+1):\n",
    "                count+=min(num//i,n)\n",
    "\n",
    "            return count\n",
    "        \n",
    "        left,right=1,m*n\n",
    "\n",
    "        while left<right:\n",
    "            mid = left+(right-left)//2\n",
    "\n",
    "            count = helper(m,n,mid)\n",
    "\n",
    "            if count>=k:\n",
    "                right=mid\n",
    "            else:\n",
    "                left=mid+1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        def check(mid):\n",
    "            num = 0\n",
    "            i, j = m, 1\n",
    "            while i >= 1 and j <= n:\n",
    "                if i * j <= mid:\n",
    "                    num += i\n",
    "                    j += 1\n",
    "                else:\n",
    "                    i -= 1\n",
    "            return num >= k\n",
    "        \n",
    "        left, right = 1, m * n\n",
    "        while left < right:\n",
    "            mid = (left + right) >> 1\n",
    "            if check(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        def get_num_less_than(target):\n",
    "            count = 0\n",
    "            for i in range(1, m + 1):\n",
    "                count += min(n, target // i)\n",
    "            return count\n",
    "\n",
    "        left, right = 1, m * n\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if get_num_less_than(mid) < k:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        def count(mid):\n",
    "            cnt = 0\n",
    "            r, c = m, 1\n",
    "            while r > 0 and c <= n:\n",
    "                if r * c <= mid:\n",
    "                    cnt += r\n",
    "                    c += 1\n",
    "                else:\n",
    "                    r -= 1\n",
    "            return cnt\n",
    "        l, r = 0, m*n\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if count(mid) < k:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        # res = []\n",
    "        # for i in range(1,m+1):\n",
    "        #     for j in range(1,n+1):\n",
    "        #         res.append(i*j)\n",
    "        # res.sort()\n",
    "        # return(res[k-1])\n",
    "        l, r = 1, m*n\n",
    "        while l < r:\n",
    "            mid = l + r >>1\n",
    "            cnt = 0  # 统计乘法表中小于等于mid的值的总数\n",
    "            for i in range(1, m + 1):  # 遍历每一行，统计。\n",
    "                cnt += min(mid//i, n)\n",
    "            if cnt < k:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        return l\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\r\n",
    "        return bisect_left(range(m * n), k, key=lambda x: x // n * n + sum(x // i for i in range(x // n + 1, m + 1)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        l, r = 1, m * n\n",
    "        if n > m:\n",
    "            m, n = n, m\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            tol = 0\n",
    "            for i in range(1,m+1):\n",
    "                tol += min(mid // i, n)\n",
    "                if tol > k:\n",
    "                    break\n",
    "            if tol >= k:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        if m > n:\n",
    "            m, n = n, m\n",
    "\n",
    "        l, r = 1, m * n\n",
    "        while l < r:\n",
    "            mid = l + (r - l) // 2\n",
    "            less_cnt, eq_cnt = 0, 0\n",
    "            for x in range(1, m + 1):\n",
    "                less_cnt += (mid - 1) // x if mid <= x * n else n\n",
    "                if mid % x == 0 and mid // x <= n:\n",
    "                    eq_cnt += 1\n",
    "            if k <= less_cnt:\n",
    "                r = mid - 1\n",
    "            elif k <= less_cnt + eq_cnt:\n",
    "                return mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        return bisect_left(range(m * n), k, key=lambda x: x // n * n + sum(x // i for i in range(x // n + 1, m + 1)))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        l, r = 1, m * n\n",
    "        while l < r:\n",
    "            x = (l + r) // 2\n",
    "            count = x // n * n  # 不超过x的个数\n",
    "            for i in range(x // n + 1, m + 1):\n",
    "                count += x // i\n",
    "            if count >= k:\n",
    "                r = x\n",
    "            else:\n",
    "                l = x + 1\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        def get(mid, m, n):\n",
    "            cnt = 0\n",
    "            for i in range(1, m + 1):\n",
    "                cnt += min(mid // i, n)\n",
    "            return cnt\n",
    "\n",
    "        l, r = 1, m * n\n",
    "        while l < r:\n",
    "            mid  = (l + r) >> 1\n",
    "            if get(mid, m, n) >= k:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        \n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\r\n",
    "        # k logm\r\n",
    "        # pq = [(i * 1, i, 1) for i in range(1, m + 1)]\r\n",
    "        # heapq.heapify(pq)\r\n",
    "\r\n",
    "        # for _ in range(k - 1):\r\n",
    "        #     num, i, j = heapq.heappop(pq)\r\n",
    "        #     # print(num, i, j)\r\n",
    "        #     if j < n:\r\n",
    "        #         heapq.heappush(pq, (num + i, i, j + 1))\r\n",
    "        # return heapq.heappop(pq)[0]\r\n",
    "\r\n",
    "        # mlogk\r\n",
    "        left, right = 1, m * n\r\n",
    "        ans = -1\r\n",
    "        while left <= right:\r\n",
    "            mid = (left + right) // 2\r\n",
    "\r\n",
    "            # count <=mid\r\n",
    "            row, col, cnt = m, 1, 0\r\n",
    "            while row > 0 and col <= n:\r\n",
    "                prod = row * col\r\n",
    "                if prod <= mid:\r\n",
    "                    cnt += row\r\n",
    "                    col += 1\r\n",
    "                else:\r\n",
    "                    row -= 1\r\n",
    "            \r\n",
    "            if cnt >= k:\r\n",
    "                ans = mid\r\n",
    "                right = mid - 1\r\n",
    "            else:\r\n",
    "                left = mid + 1\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        l = 1\n",
    "        r = m*n\n",
    "        if k>=r:\n",
    "            return r\n",
    "        def number_below_c(c):\n",
    "            num = 0\n",
    "            for i in range(1, m+1):\n",
    "                num += min(n, c//i)\n",
    "            return num>=k\n",
    "        while l<r:\n",
    "            mid = (l+r)//2\n",
    "            if number_below_c(mid):\n",
    "                r = mid \n",
    "            else:\n",
    "                l = mid + 1\n",
    "        \n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        return bisect_left(range(m * n), k, key = lambda x: x // n * n + sum(x // i for i in range(x // n + 1, m + 1)))\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        l,r = 1,m*n \n",
    "        def check(l,r,mid):\n",
    "            cnt = 0\n",
    "            for i in range(1,m+1):\n",
    "                cnt += min(n,mid//i)\n",
    "            return cnt\n",
    "\n",
    "\n",
    "        while l <r:\n",
    "            mid = (l+r)//2\n",
    "            if check(l,r,mid)>=k:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid+1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        return bisect_left(range(m * n), k, key=lambda x: x // n * n + sum(x // i for i in range(x // n + 1, m + 1)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        l, r = 1, m * n\n",
    "        def helper(target):\n",
    "            i, j = m, 1\n",
    "            cnt = 0\n",
    "            while i >= 1 and j <= n:\n",
    "                if i * j <= target:\n",
    "                    cnt += i\n",
    "                    j += 1\n",
    "                else:\n",
    "                    i -= 1\n",
    "            return cnt\n",
    "\n",
    "        while l <= r:\n",
    "            if l == r:\n",
    "                return l\n",
    "            mid = (l + r) // 2\n",
    "            count = helper(mid) \n",
    "            if count < k:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        return mid\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        def check(x):\n",
    "            ret=0\n",
    "            for i in range(1,m+1):\n",
    "                ret+=min(n,x//i)\n",
    "            return ret>=k\n",
    "        ans=bisect_left(range(m*n+1),True,key=check)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "     \n",
    "        def c(mid, k, m,n):\n",
    "\n",
    "            nu = 0\n",
    "            while m > 0:\n",
    "                b = int(mid / m)\n",
    "                nu += min(b,n)\n",
    "                m -= 1\n",
    "            return nu\n",
    "\n",
    "        l = 1\n",
    "        r = m * n\n",
    "\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "           \n",
    "            if c(mid, k, m,n) < k:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        return l\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        # left = 1\n",
    "        # right = m*n\n",
    "        # mid = (left+right)//2\n",
    "        # while left < right:\n",
    "        #     now = mid //n * n + sum(mid//i for i in range(mid//n+1, m+1))\n",
    "        #     if now < k:\n",
    "        #         left = mid+1\n",
    "        #     else:\n",
    "        #         right = mid\n",
    "        #     mid = (left+right)//2\n",
    "        # return mid\n",
    "        \n",
    "        return bisect_left(range(m*n), k, key=lambda x:x //n * n + sum(x//i for i in range(x//n+1, m+1)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "class Solution:\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        return bisect_left(range(m*n), k ,key=lambda x: x//n*n+sum(x//i for i in range(x//n+1,m+1)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        def arr(i, j):\n",
    "            return i * j \n",
    "        \n",
    "        def check(x, k):\n",
    "            i,j=m, 1\n",
    "            tot = 0 \n",
    "            while i > 0:\n",
    "                while j <= n and arr(i,j) <= x:\n",
    "                    j +=1 \n",
    "                j-=1 \n",
    "                tot += j\n",
    "                i-=1 \n",
    "            return tot >= k \n",
    "\n",
    "\n",
    "        l, r = 1, m * n \n",
    "        while l < r: \n",
    "            mid = (l + r) >> 1 \n",
    "            if check(mid, k):\n",
    "                r = mid \n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def check(self, m, n, nums):\n",
    "        return sum(min(nums // i, n) for i in range(1, m + 1))\n",
    "\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        if k == 1:\n",
    "            return 1\n",
    "        if k == m * n:\n",
    "            return m * n\n",
    "        left, right = 1, m * n\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if self.check(m, n, mid) >= k:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def count(self, m, n, mid):\n",
    "        count = 0\n",
    "        l = 1\n",
    "        while n >= 1 and l <= m:\n",
    "            if l * n <= mid:\n",
    "                l += 1\n",
    "                count += n\n",
    "            else:\n",
    "                n -= 1\n",
    "        return count\n",
    "                \n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        ma = m * n\n",
    "        mi = 1 \n",
    "        mid = (ma + mi) // 2\n",
    "        while ma > mi:\n",
    "            if self.count(m, n, mid) < k:\n",
    "                mi = mid + 1\n",
    "                mid = (ma + mi) // 2\n",
    "            else:\n",
    "                ma = mid\n",
    "                mid = (ma + mi) // 2\n",
    "        return mid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def count_num(self, m, n, num):\n",
    "        return sum(min(num // i, n)  for i in range(1, m+1))\n",
    "\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        if k == 1:\n",
    "            return 1\n",
    "        if k == m * n:\n",
    "            return m * n\n",
    "\n",
    "        left, right = 1, m * n\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if self.count_num(m, n, mid) >= k:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        left, right = 1, m * n\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            cnt = 0\n",
    "            i, j = 1, n\n",
    "            while i <= m and j >= 1:\n",
    "                while j >= 1 and i * j > mid:\n",
    "                    j -= 1\n",
    "                cnt += j\n",
    "                i += 1\n",
    "            if cnt < k:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def count_num(self, m, n, num):\n",
    "        return sum(min(num // i, n)  for i in range(1, m+1))\n",
    "\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        if k == 1:\n",
    "            return 1\n",
    "        if k == m * n:\n",
    "            return m * n\n",
    "\n",
    "        left, right = 1, m * n\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if self.count_num(m, n, mid) >= k:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        R, C = m, n\n",
    "        def check(threshold):\n",
    "            r, c, count = R - 1, 0, 0\n",
    "            while r >= 0 and c < C:\n",
    "                if (r + 1) * (c + 1) <= threshold:\n",
    "                    count += r + 1\n",
    "                    c += 1\n",
    "                else:\n",
    "                    r -= 1\n",
    "            return count >= k\n",
    "        \n",
    "        l, r, res = 1, R * C, 1\n",
    "        while l <= r:\n",
    "            m = l + (r - l) // 2\n",
    "            if check(m):\n",
    "                res = m\n",
    "                r = m - 1\n",
    "            else:\n",
    "                l = m + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findKthNumber(self,m,n,k):\r\n",
    "        l=1\r\n",
    "        r=m*n\r\n",
    "        minn=min(m,n)\r\n",
    "        maxn=max(m,n)\r\n",
    "        while l<r:\r\n",
    "            mid=(l+r)//2\r\n",
    "            sum=mid//maxn*maxn\r\n",
    "            for i in range(mid//maxn,minn):\r\n",
    "                sum+=mid//(i+1)\r\n",
    "            if sum<k:\r\n",
    "                l=mid+1\r\n",
    "            else:\r\n",
    "                r=mid\r\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        left, right = 1, m * n + 1 # right不能取到\n",
    "        while left < right: # 左闭右开\n",
    "            mid = left + (right - left) // 2\n",
    "            small_ele_num = self.countNum(m, n, mid)\n",
    "            print(mid, small_ele_num)\n",
    "            if small_ele_num > k:\n",
    "                right = mid # right取不到\n",
    "            elif small_ele_num == k:\n",
    "                right = mid # mid可能并不存在在乘法表里，要找最小的数字\n",
    "            elif small_ele_num < k:\n",
    "                left = mid + 1\n",
    "        return left # left == right\n",
    "    \n",
    "    def countNum(self, m, n, target):\n",
    "        # 统计<=target的数字数量\n",
    "        count = 0\n",
    "        for i in range(1, m + 1):\n",
    "            count += min(target // i, n)\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#!/usr/bin/python\n",
    "# -*- encoding: utf-8 -*-\n",
    "'''\n",
    "@File    :   669.乘法表中第k小的数.py\n",
    "@Time    :   2023/09/29 11:28:56\n",
    "@Author  :   Yuan\n",
    "'''\n",
    "\n",
    "\n",
    "from typing import List\n",
    "from sortedcontainers import SortedDict, SortedKeyList\n",
    "from functools import cache, lru_cache\n",
    "from collections import deque, Counter, OrderedDict \n",
    "from bisect import bisect_left, bisect_right\n",
    "import heapq\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        def check(x):\n",
    "            s = 0\n",
    "            for i in range(1, n+1):\n",
    "                if x // i > 0:\n",
    "                    s += min( x // i, m )\n",
    "                else:\n",
    "                     break \n",
    "            if s < k:\n",
    "                return False \n",
    "            else:\n",
    "                return True \n",
    "        return bisect_left(range(int(m * n + 10)), True, key=check)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        l = 1\n",
    "        r = m*n\n",
    "\n",
    "        while l<r:\n",
    "            mid = (l+r)//2\n",
    "            cnt = sum([min(mid//i, n) for i in range(1, m+1)])\n",
    "            if cnt<k:\n",
    "                l = mid+1\n",
    "            else:\n",
    "                r = mid\n",
    "\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        l = 1\n",
    "        r = m*n\n",
    "\n",
    "        while l<r:\n",
    "            mid = (l+r)//2\n",
    "            cnt = sum([min(mid//row, n) for row in range(1, m+1)])\n",
    "            if cnt<k:\n",
    "                l = mid+1\n",
    "            else:\n",
    "                r = mid\n",
    "\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, m: int, n: int, k: int) -> int:\n",
    "        l = 1\n",
    "        r = m*n\n",
    "\n",
    "        while l<r:\n",
    "            x = (l+r)//2\n",
    "            cnt = sum([min(x//i, n) for i in range(1, m+1)])\n",
    "            if cnt<k:\n",
    "                l = x+1\n",
    "            else:\n",
    "                r = x\n",
    "\n",
    "        return l"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
